import numpy as np


def min(a, b, c):
    if a <= b and a <= c:
        return a, 0
    elif b <= a and b <= c:
        return b, -1
    elif c <= a and c <= b:
        return c, 1


def distance(x, y):
    if (x.shape == y.shape):
        d = x - y
        # print(d)
        distance = np.linalg.norm(d, 2, None, False)

        return distance
    else:
        print("数据格式未对齐")
        return


def dtw_distance(ts_a, ts_b, d=distance, mww=np.inf):
    M, N = len(ts_a), len(ts_b)
    cost = np.zeros((M, N), dtype=float)

    cost[0, 0] = d(ts_a[0], ts_b[0])
    for i in range(1, M):
        cost[i, 0] = cost[i - 1, 0] + d(ts_a[i], ts_b[0])
    for j in range(1, N):
        cost[0, j] = cost[0, j - 1] + d(ts_a[0], ts_b[j])
    # Populate rest of cost matrix within window
    for i in range(1, M):
        for j in range(1, N):
            # print(d(ts_a[i],ts_b[i]))
            choice, index = min(cost[i - 1, j - 1], cost[i, j - 1], cost[i - 1, j])
            cost[i, j] = choice + d(ts_a[i], ts_b[j])
    return cost[-1, -1]


def dtw_warp(ts_a, ts_b, d=distance, mww=np.inf):
    M, N = len(ts_a), len(ts_b)
    cost = np.zeros((M, N), dtype=float)
    ptr = np.zeros((M, N), dtype=int)

    cost[0, 0] = d(ts_a[0], ts_b[0])
    for i in range(1, M):
        cost[i, 0] = cost[i - 1, 0] + d(ts_a[i], ts_b[0])
        ptr[i, 0] = 1
    for j in range(1, N):
        cost[0, j] = cost[0, j - 1] + d(ts_a[0], ts_b[j])
        ptr[0, j] = -1
    # Populate rest of cost matrix within window
    for i in range(1, M):
        for j in range(1, N):
            choice, pointer = min(cost[i - 1, j - 1], cost[i, j - 1], cost[i - 1, j])
            cost[i, j] = choice + d(ts_a[i], ts_b[j])
            ptr[i, j] = pointer
    i = M - 1
    j = N - 1
    warp_ts = [None] * N
    while (i >= 0 and j >= 0):
        if ptr[i, j] == 0:
            warp_ts[j] = ts_a[i]
            i -= 1
            j -= 1
        elif ptr[i, j] == -1:
            warp_ts[j] = ts_a[i]
            j -= 1
        elif ptr[i, j] == 1:
            sum = float(0)
            num = float(0)
            while (ptr[i, j] == 1):
                sum += ts_a[i]
                num += 1
                i -= 1
            warp_ts[j] = sum / num
            j -= 1
    return warp_ts


if __name__ == '__main__':
    x = np.random.ranf((19, 1))
    y = np.random.ranf((24, 1))
    # print(len(x))
    # print(len(y))
    print(x)
    print(y)
    print(dtw_warp(x, y, distance))
